/**
 * 寻找重复数#287
 */
public class FindingDuplicates {
    public static void main(String[] args) {
        int[] test1  = {1,3,4,2,2};
        int[] test2  = {3,1,3,4,2};
        int[] test3  = {3,3,3,3,3};
        System.out.println(findDuplicateBinarySearch(test1));
        System.out.println(findDuplicateBinarySearch(test2));
        System.out.println(findDuplicateBinarySearch(test3));

    }

    /**
     * 二分查找法
     */
    public static int findDuplicateBinarySearch(int[] nums) {
        int left = 1;
        int right = nums.length -1;

        while(left <= right){
            int mid = (left + right)/2;
            int count = 0;
            for (int num : nums) {
                if(num <= mid){
                    count++;
                }
            }
            if(count <= mid){
                left = mid+1;
            }else {
                right = mid;
            }

            if(left == right){
                return left;
            }
        }
        return -1;
    }

}
